package problem.year2022.Month12;

import java.util.*;

/**
 * @author LiangMu
 * @version \$Id: D1219.java, v 0.1, 2022年12月19日 16:12 LiangMu Exp $$
 */
public class D1219 {
    public static void main(String[] args) {
        int[][] ints = new int[][]{{1, 2}, {3, 4}};
        int[][] res = matrixReshape(ints, 1, 4);
        for (int[] it : res) {
            System.out.println(Arrays.toString(it));
        }
    }

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] chars1 = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char it : chars1) {
            map.put(it, map.getOrDefault(it, 0) + 1);
        }
        char[] chars2 = t.toCharArray();
        for (char it : chars2) {
            if (!map.containsKey(it)) return false;
            int val = map.get(it) - 1;
            if (val < 0) return false;
            map.put(it, val);
        }
        return true;
    }

    public int firstUniqChar(String s) {
        char[] chars = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char it : chars) {
            map.put(it, map.getOrDefault(it, 0) + 1);
        }
        for (int i = 0; i < chars.length; i++) {
            if (map.get(chars[i]) == 1) {
                return i;
            }
        }
        return -1;
    }

    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = magazine.toCharArray();
        for (char it : chars) {
            map.put(it, map.getOrDefault(it, 0) + 1);
        }
        char[] charArray = ransomNote.toCharArray();
        for (char it : charArray) {
            int val = map.getOrDefault(it, 0) - 1;
            if (val < 0) return false;
            map.put(it, val);
        }
        return true;
    }

    public void setZeroes(int[][] matrix) {
        int len = matrix.length;
        if (len <= 0) {
            return;
        }
        StringJoiner point = new StringJoiner(";");
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    point.add(String.format("%d:%d", i, j));
                }
            }
        }
        String[] split = point.toString().split(";");
        for (String s : split) {
            String[] points = s.split(":");
            int x = Integer.parseInt(points[0]);
            int y = Integer.parseInt(points[1]);
            for (int i = 0; i < matrix[0].length; ++i) {
                matrix[x][i] = 0;
            }
            for (int i = 0; i < matrix.length; ++i) {
                matrix[i][y] = 0;
            }
        }
    }

    public boolean isValidSudoku(char[][] board) {
        // 判断行是否是数独
        Set<Character> set = new HashSet<>();
        for (char[] it : board) {
            for (char c : it) {
                if (c != '.') {
                    boolean add = set.add(c);
                    if (!add) return false;
                }
            }
            set.clear();
        }
        // 判断列
        int len = board[0].length;
        for (int i = 0; i < len; ++i) {
            for (char[] it : board) {
                if (it[i] != '.') {
                    boolean add = set.add(it[i]);
                    if (!add) return false;
                }
            }
            set.clear();
        }
        // 判断单元格
        for (int i = 0; i < len / 3; ++i) {
            int cIndex = i * 3;
            for (int j = 0; j < len / 3; ++j) {
                int rIndex = j * 3;
                for (int k = 0; k < 2; ++k) {
                    if (board[cIndex + k][rIndex] != '.') {
                        boolean add = set.add(board[cIndex + k][rIndex]);
                        if (!add) return false;
                    }
                    if (board[cIndex + k][rIndex + 1] != '.') {
                        boolean add = set.add(board[cIndex + k][rIndex + 1]);
                        if (!add) return false;
                    }
                    if (board[cIndex + k][rIndex + 2] != '.') {
                        boolean add = set.add(board[cIndex + k][rIndex + 2]);
                        if (!add) return false;
                    }
                }
                set.clear();
            }
        }
        return true;
    }

    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 1; i <= numRows; ++i) {
            List<Integer> row = new ArrayList<>(i);
            for (int j = 0; j < i; ++j) {
                if (j == 0 || j == i - 1) {
                    row.add(1);
                } else {
                    row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                }
            }
            res.add(row);
        }
        return res;
    }

    public static int[][] matrixReshape(int[][] mat, int r, int c) {
        if (mat.length * mat[0].length != r * c) {
            return mat;
        }
        int[][] res = new int[r][c];
        int count = 0, clen = mat[0].length;
        for (int[] ints : mat) {
            for (int j = 0; j < clen; ++j) {
                res[count / c][count % c] = ints[j];
                ++count;
            }
        }
        return res;
    }

    public static int maxProfit2(int[] prices) {
        int min = prices[0], max = -prices[0];
        int len = prices.length;
        for (int i = 1; i < len; ++i) {
            int price = prices[i];
            min = Math.min(price, min);
            max = Math.max(price - min, max);
        }
        return max;
    }

    public static int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = prices[0];
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; ++i) {
            int price = prices[i];
            dp[i][0] = Math.min(dp[i - 1][0], price);
            dp[i][1] = Math.max(price - dp[i][0], dp[i - 1][1]);
        }
        return dp[len - 1][1];
    }

    public int[] intersect1(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int it : nums1) {
            if (map.containsKey(it)) {
                map.put(it, map.get(it) + 1);
            } else {
                map.put(it, 1);
            }
        }
        List<Integer> ints = new ArrayList<>();
        for (int it : nums2) {
            if (map.containsKey(it)) {
                Integer count = map.get(it);
                if (count > 0) {
                    ints.add(it);
                    map.put(it, count - 1);
                }
            }
        }
        return ints.stream().mapToInt(it -> it).toArray();
    }

    public int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i1 = 0, i2 = 0;
        List<Integer> res = new ArrayList<>();
        while (i1 < nums1.length && i2 < nums2.length) {
            int r1 = nums1[i1], r2 = nums2[i2];
            if (r1 == r2) {
                res.add(r1);
                ++i1;
                ++i2;
            } else if (r1 < r2) {
                ++i1;
            } else {
                ++i2;
            }
        }
        return res.stream().mapToInt(it -> it).toArray();
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int lastIndex = m + n - 1;
        int i1 = m - 1, i2 = n - 1;
        while (i1 >= 0 && i2 >= 0) {
            int r1 = nums1[i1], r2 = nums2[i2];
            if (r1 > r2) {
                nums1[lastIndex--] = r1;
                --i1;
            } else {
                nums1[lastIndex--] = r2;
                --i2;
            }
        }
        if (i1 < 0) {
            if (i2 + 1 >= 0) System.arraycopy(nums2, 0, nums1, 0, i2 + 1);
        }
    }

    // 广度探索
    public boolean validPath1(int n, int[][] edges, int source, int destination) {
        if (source == destination) return true;
        Map<Integer, Set<Integer>> map = new HashMap<>(n);
        for (int[] it : edges) {
            int key = it[0];
            int val = it[1];
            if (map.containsKey(key)) {
                map.get(key).add(val);
            } else {
                HashSet<Integer> integers = new HashSet<>();
                integers.add(val);
                map.put(key, integers);
            }
            if (map.containsKey(val)) {
                map.get(val).add(key);
            } else {
                HashSet<Integer> integers = new HashSet<>();
                integers.add(key);
                map.put(val, integers);
            }
        }
        Set<Integer> set = map.get(source);
        map.put(source, null);
        while (set != null && !set.isEmpty()) {
            if (set.contains(destination)) {
                return true;
            }
            Set<Integer> tmp = new HashSet<>();
            set.forEach(it -> {
                Set<Integer> integers = map.get(it);
                if (integers != null) {
                    tmp.addAll(integers);
                }
            });
            set = tmp;
        }
        return false;
    }

    // 深度探索
    public boolean validPath2(int n, int[][] edges, int source, int destination) {

        return false;
    }

    class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int n) {

        }
    }
}
